The Internet is arranged so that a computing device can have a unique name or address by which it can be identified. When data is transmitted over the Internet between computing devices, it is generally broken down into smaller groupings called “packets”. In addition to the data which is being transmitted, the packets will normally include important transmission information such as the sender's identity or Internet Packet Address (IP Address), the addressee or intended recipient's IP Address, the actual data (or data request), and so on.
Each packet transmitted from a user's computing device will typically travel through several network devices such as hubs, switches, and routers. If a user's computing device is part of a local area network, the packet will generally travel along a cable until it arrives at a hub to which the cable is connected. The hub or “repeater” as it is sometimes called, will retransmit the packet to another network device (such as a switch) until the packet reaches a router. The router examines the information transmitted with the packet and determines the best way for it to get to its destination.
Once the router has determined how the packet is to be sent, it selects another router at some other location and transmits the message to the router in the direction the packet is intended to travel. For example, if the message is going from New York to California, the router might send the packet to a router located in an intermediate city such as Chicago along a high speed communication channel. Once there, another router will determine a subsequent router to which the packet will be sent next. In this way, the packet is transmitted from router to router until the packet has nearly reached its destination.
When the packet is near to its destination, it is eventually passed to a local hub, which retransmits the message to its intended recipient computing device. The recipient computing device then reassembles the packet with other parts of the original message to create the complete set of transmitted data. Thus, a router functions in a network by connecting wide area networks and local area networks to allow traffic and communication of packet information to be transmitted to selected destinations.
In addition, there are different types of routers that may be used in a given network. For instance, one type of router may employ a first-in-first-out (FIFO) buffer to schedule the forwarding of packets. In this case, the packet forwarding is generally dictated by the dynamic properties of TCP (Transmission Control Protocol), which is the transport protocol used in most IP networks. Another type of router may forward different types of packet flows with weighted queues that are associated with a differentiated service (DiffServ). This type of router is often used to provide minimum bandwidth guarantees for particular flows of packets while achieving a very high level of resource utilization. These packet flows could include data for streaming media, signaling and interactive, e.g., file transfers and browsing.
However, when a particular weighted queue reaches maximum capacity due to some overload condition, packets in the queue are typically dropped by the router, i.e., the packets are discarded and not forwarded to their destination. Packets associated with a particular flow in a weighted queue that is overloaded may be dropped even when another weighted queue associated with a different flow of packets may be operating at less than maximum capacity. Accordingly, while an overload condition occurs, it would be desirable to shift a flow of packets from an overloaded weighted queue to another weighted queue that is under utilized until the overload condition ends. It is with respect to these considerations and others that the present invention has been made.